#include<iostream>
#include<vector>
using namespace std;
const int N = 1010;
int n, m;
int a, b, c;
typedef pair<int, int> PII;
int f[N];
vector<PII> g[N];
int main()
{
	cin >> m>>n;
	int cnt = 0;
	for (int i = 1;i <= n;i++)
	{
		cin >> a >> b >> c;//a是重量，b是价值
		//把这个物品插入到对应的组里面
		cnt = max(cnt, c);
		g[c].push_back({ a,b });
	}
	//for (int i = 1;i <= cnt;i++)//i表示前i个组
	//{
	//	for (int j = m;j >= 0;j--)//表示重量不超过j
	//	{
	//		//不选这一组的
	//		f[i][j] = f[i - 1][j];
	//		//选的话直接遍历这一组
	//		for (auto& t : g[i])
	//		{
	//			int a = t.first;//PII的first不加括号
	//			int b = t.second;
	//			if (a <= j)
	//			{
	//				f[i][j] = max(f[i][j], f[i - 1][j - a] + b);
	//			}
	//		}
	//	}
	//}
	for (int i = 1;i <= cnt;i++)//i表示前i个组
		{
			for (int j = m;j >= 0;j--)//表示重量不超过j
			{
				//不选这一组的
				f[j] = f[j];
				//选的话直接遍历这一组
				for (auto& t : g[i])
				{
					int a = t.first;//PII的first不加括号
					int b = t.second;
					if (a <= j)
					{
						f[j] = max(f[j], f[j - a] + b);
					}
				}
			}
		}
	cout << f[m] << endl;
}